package 剑指专题.搜索算法;


/*
 * Author：江松
 * Date：2023/3/31 21:11
 *
 机器人的运动范围：
 1，广度优先搜索
 */

import java.util.LinkedList;
import java.util.Queue;

public class Main6 {

    class node{
        int x,y;
        public node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    private boolean vis[][];
    private int dx[]={0,0,1,-1};
    private int dy[]={1,-1,0,0};

    public int bitVal(int x){
        int res=0;
        while(x!=0){
            res+=x%10;
            x/=10;
        }
        return res;
    }

    public int movingCount(int threshold, int rows, int cols) {
        Queue<node>queue=new LinkedList<>();
        queue.offer(new node(0,0));
        vis=new boolean[rows][cols];
        vis[0][0]=true;
        int res=1;
        while(!queue.isEmpty()){
            node t=queue.poll();
            System.out.println(t.x+","+t.y);
            for(int i=0;i<4;++i){
                int xx=dx[i]+t.x;
                int yy=dy[i]+t.y;
                if(xx>=0&&xx<rows&&yy>=0&&yy<cols&&!vis[xx][yy]&&bitVal(xx)+bitVal(yy)<=threshold){
                    vis[xx][yy]=true;
                    queue.offer(new node(xx,yy));
                    res++;
                }
            }
        }
        return res;
    }
}
